# -*- coding: utf-8 -*-

"""
You are asked to cut off trees in a forest for a golf event. The forest is represented as a non-negative 2D map, in this map:

0 represents the obstacle can't be reached.
1 represents the ground can be walked through.
The place with number bigger than 1 represents a tree can be walked through, and this positive number represents the tree's height.
You are asked to cut off all the trees in this forest in the order of tree's height - always cut off the tree with lowest height first. And after cutting, the original place has the tree will become a grass (value 1).

You will start from the point (0, 0) and you should output the minimum steps you need to walk to cut off all the trees. If you can't cut off all the trees, output -1 in that situation.

You are guaranteed that no two trees have the same height and there is at least one tree needs to be cut off.

Example 1:
Input:
[
 [1,2,3],
 [0,0,4],
 [7,6,5]
]
Output: 6
Example 2:
Input:
[
 [1,2,3],
 [0,0,0],
 [7,6,5]
]
Output: -1
Example 3:
Input:
[
 [2,3,4],
 [0,0,5],
 [8,7,6]
]
Output: 6
Explanation: You started from the point (0,0) and you can cut off the tree in (0,0) directly without walking.
Hint: size of the given matrix will not exceed 50x50.

"""
import heapq
import time
import collections

class Solution(object):
    def cutOffTree(self, forest):
        """
        :type forest: List[List[int]]
        :rtype: int
        """

        m = len(forest)
        n = len(forest[0])

        def checkcord(cord):
            return 0 <= cord[0] < m and 0 <= cord[1] < n

        def neighbors(cord):
            return [x for x in [(i + cord[0], j + cord[1]) for i, j in [(-1, 0), (1, 0), (0, -1), (0, 1)]] if checkcord(x)]

        def manhattan(start, end):
            """
            曼哈顿距离
            :param start:
            :param end:
            :return:
            """
            return abs(start[0] - end[0]) + abs(start[1] - end[1])


        def bd_dfs(start, end):
            """
            双向BFS
            :param start:
            :param end:
            :return:
            """
            if start == end:
                return 0

            step = 0
            p = {start}
            pvisited = {start}
            q = {end}
            qvisited = {end}

            while q and q:
                pnext = set()
                for loc in p:
                    for b in neighbors(loc):
                        if forest[b[0]][b[1]] != 0 and b not in pvisited:
                            pnext.add(b)

                qnext = set()
                for loc in q:
                    for b in neighbors(loc):
                        if forest[b[0]][b[1]] != 0 and b not in qvisited:
                            qnext.add(b)

                if pvisited & qnext or qvisited & pnext:
                    return step + 1

                if pnext & qnext:
                    return step + 2

                p = pnext
                q = qnext
                pvisited |= pnext
                qvisited |= qnext

                step += 2

            return float('inf')

        # Distance from (i, j) to (I, J).
        def distance(start, end):
            i, j = start
            I, J = end
            now, soon = [(i, j)], []
            expanded = set()
            manhattan = abs(i - I) + abs(j - J)
            detours = 0
            while True:
                if not now:
                    now, soon = soon, []
                    detours += 1
                i, j = now.pop()
                if (i, j) == (I, J):
                    return manhattan + 2 * detours
                if (i, j) not in expanded:
                    expanded.add((i, j))
                    for i, j, closer in (i + 1, j, i < I), (i - 1, j, i > I), (i, j + 1, j < J), (i, j - 1, j > J):
                        if 0 <= i < m and 0 <= j < n and forest[i][j]:
                            (now if closer else soon).append((i, j))
        def astar(start, end):
            if start == end:
                return 0

            q = []
            visited = {start}
            tovisit = {}
            heapq.heapify(q)
            heapq.heappush(q, (manhattan(start, end), 0, start))
            while q:
                ld, d, loc = heapq.heappop(q)
                d = -d
                if loc == end:
                    return d

                visited.add(loc)
                for b in neighbors(loc):
                    if forest[b[0]][b[1]] != 0 and b not in visited:
                        estd = manhattan(b, end) + d + 1
                        if b in tovisit:
                            if estd < tovisit[b]:
                                tovisit[b] = estd
                                # 这里没有删除以前遍历过的点
                                heapq.heappush(q, (estd, -(d+1), b))
                        else:
                            tovisit[b] = estd
                            # 估计距离一样的时候，先遍历走过的最长的路径
                            heapq.heappush(q, (estd, -(d+1), b))

            return float('inf')

        heights = list(sorted(filter(lambda x: x[0] > 1, [(forest[i][j], (i, j)) for i in range(m) for j in range(n)])))

        # can we reach every tree?
        q = [(0,0)]
        reached = set()
        for i, j in q:
            if (i, j) not in reached and forest[i][j]:
                reached.add((i, j))
                for ni, nj in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
                    if 0 <= ni < m and 0 <= nj < n:
                        q.append((ni, nj))
        if not all((i, j) in reached for (_, (i, j)) in heights):
            return -1

        positions = [(0, 0)] + [x[1] for x in heights]
        res = sum([distance(positions[i], positions[i+1]) for i in range(len(positions)-1)])
        # res = sum([bd_dfs(positions[i], positions[i + 1]) for i in range(len(positions) - 1)])
        return -1 if res == float('inf') else res




s = Solution()
t0 = time.time()
print(s.cutOffTree([[46362,32601,72983,56271,26019,54579,55962,9265,88322,18670,41215,78738,81679,87588,53871,66445,99225,27506,3615,95487,18069,49495,2877,56179,75642,40368,87500,49278,99866,0,9449,0,9522,0,56248,19930,21867,11439,0,52676,56754,51753,24701,27123,13273,91666],[0,59813,50534,36242,89504,75119,3385,67530,49880,37837,46715,91665,95908,3726,1932,55941,47642,47920,64825,93084,76640,44212,86456,30435,78039,25760,82843,0,6033,12185,26840,98131,43430,47234,16305,27915,76703,67226,70358,43260,82426,95791,19429,77090,81763,0],[0,36720,9104,48681,0,80757,41932,97191,34686,95820,0,68754,25307,81711,73455,0,19617,93418,25745,32919,95526,6224,32030,46278,28922,28305,0,43103,43580,89708,72013,35319,5851,24141,0,14749,77548,49903,81317,50344,78205,52211,26552,72879,19021,45821],[43458,65381,88583,62464,97622,71580,72944,34392,0,185,95764,43399,68766,48343,87995,21368,92607,69010,35964,77570,27203,77846,75268,67281,64968,43684,81403,79166,63798,42979,72419,33675,73288,48664,85453,60452,73368,56563,99717,72472,0,81703,71587,88921,5927,51849],[20843,88732,0,40528,38717,72244,76375,93155,58889,56653,0,0,65375,13138,32418,55653,39433,0,60849,74015,1462,58671,22683,68027,61146,79440,17292,52738,45086,9670,63511,27523,35429,65629,14642,8124,27913,53756,46631,65883,85166,6630,84843,93640,59374,0],[90616,25023,15484,70526,0,22650,34140,67954,8631,47379,49237,0,15607,38770,86621,749,44652,11733,11028,43888,32021,61905,55124,45832,51758,62451,32792,27606,69752,40098,88003,74610,65551,92944,29761,30517,57646,98223,89163,9547,49981,84873,37057,16684,35376,60240],[31193,11652,77021,76747,60128,42576,30632,18033,58469,72620,93687,60024,71037,46028,56309,31934,24754,75493,18583,32878,51833,80661,0,15514,0,93378,57887,54215,26472,6085,0,4780,59883,53806,4296,31077,55775,36401,55882,55150,59639,95141,1381,24963,7742,4003],[84527,23383,31289,75203,32550,53847,0,84820,21123,40746,38512,93451,0,50096,42762,52399,96383,77025,92952,15612,6250,58965,24868,98677,5525,66483,36444,0,74651,80219,72831,0,75826,0,4093,19792,98183,43650,18331,0,22142,99350,13156,14370,21712,72105],[97532,90324,39327,19710,76671,15615,51068,54665,98170,7730,20769,0,0,0,5644,1073,29465,15464,78962,23743,16732,38414,95993,98746,38536,29898,28483,48156,36175,33658,41227,56736,29029,89126,15061,25069,0,62420,16179,98750,59393,88069,5427,57938,26851,21467],[79811,48859,89207,84657,98629,23226,11397,60318,33335,70539,63274,69251,62005,73916,5870,80674,40396,56405,15030,66667,80228,96489,8293,41755,21022,32841,39127,80843,66831,82566,87014,20504,53735,82156,93963,13182,70990,83827,9755,46258,39986,49700,34150,7946,41889,3167],[35132,69623,82837,11431,16570,0,0,518,72859,50481,27067,12108,75538,43783,11990,79370,14093,45881,25264,9965,74005,72922,17241,0,3560,2959,50462,26989,30349,3654,24450,98956,0,51334,32852,37513,41701,0,70269,0,8540,56682,34693,8836,0,0],[58610,23874,66034,36824,93714,48725,51586,25845,50559,99348,49905,53039,38489,41876,59254,50948,0,68688,92062,6961,52517,97926,0,72147,30962,47894,40458,75512,52707,15791,75497,39600,89816,3682,89264,23051,0,14692,80758,50378,23815,30459,37486,65247,0,82019],[31927,35711,25283,57833,66702,81681,79334,90272,47505,14230,94947,72966,80642,35578,67715,9697,39595,43237,35977,89748,38053,94374,45653,24676,1948,23962,58505,0,32939,93120,68579,59688,69169,0,0,75317,81142,0,34733,81476,40515,8286,55858,84242,43788,6724],[24146,23036,55367,45476,19404,71171,2630,27268,61312,92848,7255,0,99686,34139,3331,53095,36734,40921,63523,53778,16340,0,41880,98129,45389,38890,44870,70721,7334,66174,0,33215,22704,15023,7995,17955,7337,51052,14687,5101,33132,50849,39228,46147,43959,35730],[31163,5996,62467,84890,45084,47038,0,94610,65242,66684,4943,13223,81734,68088,58500,86359,93937,66079,16881,26040,43526,46860,69234,87554,0,493,42723,8592,33483,82562,34108,33402,67438,22173,46230,80130,63174,62923,83423,50918,81205,53399,0,22640,82760,0],[98016,58605,33591,75113,0,31825,82446,81377,6212,1917,83674,60395,85818,25455,72241,87366,9807,11103,12623,12790,1762,10858,69611,1660,20471,90015,75995,1631,51358,64489,19170,54343,57218,55654,68178,19368,27267,26549,54877,16652,34907,36209,37527,90617,52618,57384],[26333,48249,90583,17598,82582,73061,55646,51202,65721,3971,46997,55536,11077,56463,58740,60933,10781,52155,0,0,24355,8039,16680,74110,43407,49065,46238,58441,29439,83473,5862,69296,4835,52626,49250,22043,10419,53409,78763,14652,9369,0,59810,90689,73700,39537],[71101,9304,22081,29507,0,96347,84083,72384,3559,65817,15459,1333,0,59822,89022,26247,77433,0,0,81007,11493,2186,0,9150,71751,98601,53112,53309,0,51524,85271,8801,0,62698,37237,0,21367,24272,84249,81730,12570,30755,84706,856,0,0],[95543,62573,22706,83126,15518,65153,85786,85749,49523,0,30559,4494,40657,73574,83650,31573,3318,51192,26048,48369,0,96208,89440,42574,85977,98957,16947,80749,0,17312,85049,93257,3789,48769,54894,52642,44520,66926,34191,56854,40851,93327,95613,83233,6154,18649],[87860,6636,0,43588,77305,63296,41833,41914,37240,0,15984,99788,49236,83928,78551,0,42701,39942,99989,5924,78111,0,97775,32524,76154,36999,66460,22796,33984,26528,51408,17421,53338,62388,95228,43603,64451,87941,94266,0,0,87447,89499,2179,61061,20003],[91597,71756,82998,69619,33,70878,58114,29534,2109,73309,26962,85814,31362,60634,92086,39110,72653,55407,0,24902,0,99059,2122,1955,53429,2650,12488,78437,23707,40010,91799,19334,68929,0,64495,68565,0,84733,62663,78825,37857,19614,51072,8386,99829,77586],[61847,49644,10274,0,46493,65133,53149,0,53589,0,16842,49773,28961,30907,32322,43521,2399,30476,39206,54335,53141,0,72785,94148,95203,0,72561,58725,20254,0,81169,60730,72639,83043,90049,32111,88797,57419,59744,20274,35027,6624,4862,28278,65020,96646],[75423,29958,32062,0,1911,64071,72881,22685,0,9246,67591,57583,25995,0,83497,56235,50166,0,13637,17808,68495,70064,93018,45367,62294,49462,0,15710,88161,72884,27456,72510,77598,41113,72352,2418,50967,9418,99478,34024,62251,13563,52753,85850,10096,61172],[0,95038,5586,47467,14761,41168,18815,0,27985,1003,8506,41766,98453,98023,46447,42254,82297,0,59488,34414,61386,89468,4826,44564,76252,13598,11575,61341,0,0,97671,81426,88124,19410,76656,89987,7517,30117,11705,0,47330,0,21906,75425,49263,0],[95595,38998,3226,24205,7066,41074,5286,31410,94303,26763,31746,19719,4746,87424,42634,67696,36045,72937,86353,21829,0,55724,90664,43180,79510,14840,53997,83326,74825,51689,41554,66400,69897,7082,56143,57374,76928,21386,0,0,36714,11042,99896,40424,37892,0],[19381,28212,15293,76333,46496,80441,99364,70212,80941,94267,68080,82258,80063,72577,39584,86593,49621,4417,0,93563,93258,68140,3128,98146,17017,23900,33384,18214,10047,70846,57522,39097,13298,0,70059,55219,54367,79630,50594,0,12631,3928,74058,18901,0,22546],[10784,68542,43563,18513,44045,70444,8637,69126,64967,47994,41171,0,76189,0,42527,0,52329,78713,73201,38971,23940,0,9422,71408,30438,31446,76268,0,17462,68787,53201,35661,0,32501,91466,31655,11792,47540,4311,34129,82423,78278,6697,31567,0,72345],[8510,11791,0,0,83096,77890,15120,23783,30820,9712,39751,0,0,52402,52480,67785,17264,94992,53071,94774,0,79990,35329,0,97986,53,92857,16428,43878,7422,51426,29894,94689,27616,30152,39750,1900,87572,63078,90209,36576,99352,7807,16228,57639,41119],[27899,32917,97673,58341,99007,64423,63471,55645,67413,36233,62277,0,65051,0,28001,76276,9729,52272,2698,66826,31240,58337,67096,4014,20983,76888,68902,3793,61140,34625,66292,30789,12987,50801,90538,53859,94871,17610,96199,11927,36636,93414,53274,0,5555,6156],[54227,19589,0,92050,78588,26306,21750,34917,82965,91386,42485,49477,58180,0,0,49085,33088,18401,51138,24140,80185,76484,3650,12768,68720,84017,44431,95660,22267,89678,25867,66470,92222,10447,63920,96116,6394,0,76511,0,20654,93695,0,98951,21427,56493],[85138,1237,0,41186,38003,6754,37315,42462,94886,62620,0,9518,94961,96466,71927,26807,24107,55533,62356,0,57504,92209,18832,0,97452,41767,51286,39898,66306,56303,35171,88178,51234,95000,0,73160,71565,39664,27192,6425,40710,0,3255,99148,74411,0],[25984,30904,72902,50012,4956,27287,81445,27838,69620,8647,631,16260,19072,99772,33423,69628,0,37332,91505,71459,75932,24543,85791,19702,0,1228,0,39834,38891,14480,0,58301,77271,31657,95704,22635,42060,11680,61588,67799,85896,91046,0,11954,45575,28376],[54203,21037,17827,80405,19904,0,5110,29623,23851,49765,61403,21351,12089,0,12013,38702,58762,56502,0,19271,0,90019,78590,46829,0,53464,96316,12308,58957,5223,0,27427,84000,11485,42987,32851,85227,99034,88629,9723,12300,6356,16321,27235,12348,74032],[10109,89134,94814,27281,94770,4416,28619,10602,53654,18235,1867,86825,2077,84328,97612,41908,92926,53455,64350,75053,61568,96648,33910,1715,81394,97958,20017,77842,84951,51930,82572,87159,59204,26034,77574,65307,37355,10441,30314,7709,93391,87300,13433,96305,51305,48301],[38764,63368,95762,92526,71199,0,64251,15811,87527,6317,14705,83736,0,86117,50368,63777,68210,101,0,74481,46018,28948,93457,39563,0,78311,3701,11837,9727,0,0,0,27451,87461,43957,58053,9588,39489,31688,50500,50073,72179,20791,89275,53949,21060],[92235,0,68152,46553,70590,61047,0,62670,11503,68620,36064,45890,57596,16878,49009,34300,28272,94810,60111,55043,84364,37769,81608,16592,53574,26111,35191,0,51562,31608,47706,15650,96829,12407,53287,26723,24176,52563,0,76423,43662,81022,20946,8507,72583,0],[26965,36862,58523,90028,11428,34761,0,42336,59269,71454,62020,69198,24522,24813,49170,20870,48164,52646,96090,93105,83206,71542,55038,33600,6353,39064,73433,98658,18159,91491,68098,96482,63189,0,76108,85168,0,69922,48395,3896,87925,0,36695,38917,83352,38921],[86315,47106,23919,67077,87956,39793,56040,93364,31548,36528,2965,55354,15808,87611,46650,82646,71002,93173,67218,0,0,48896,92130,2678,49304,84241,45430,93254,11631,6908,23633,40297,68310,30697,95721,85511,74839,37865,95733,0,34601,0,91727,27034,12847,61117],[92547,37519,35465,14947,4102,47985,14339,47917,393,68337,47686,90645,30055,41824,28719,59927,41954,68278,74783,52020,41187,79744,56932,30529,70758,75948,6104,28046,47162,16301,77770,11442,59549,0,210,98233,34843,50690,27036,18315,40288,79906,66371,8559,27964,12206],[55904,59108,57782,17674,6606,86189,56916,17333,19160,8151,93949,17407,39721,48767,61477,38864,15479,1647,79672,8959,86798,15372,40929,53312,55083,836,95452,42863,99103,0,87385,53025,94182,47943,82115,53953,35272,94030,62154,7076,32885,46681,0,0,23856,98390],[0,47978,45522,66444,72184,32078,47482,89875,84301,74922,66251,17128,56726,49634,47381,95822,11282,46163,42659,80896,49890,81924,7458,65009,76820,61507,0,83896,48298,83752,79490,31425,83673,55379,43124,24637,3058,46919,18029,99883,0,73591,1545,41538,46296,509],[57974,41984,4569,74089,79047,92762,90915,0,0,94229,46074,31922,4994,96309,10933,1584,0,88172,60623,22982,73479,75138,89763,87254,17983,61999,41389,28835,31155,10319,69386,88528,92846,0,37381,53617,60067,93960,12475,19059,45351,89111,69065,76215,22304,33191],[32100,54614,25922,0,0,9923,1925,93317,81622,0,12842,37110,76784,0,56752,85362,0,85047,27460,15748,98520,81526,54790,31102,0,12000,26736,30666,55528,45686,82908,13655,22010,0,67239,11243,42008,3361,28845,93475,25237,71761,18845,57825,0,22699],[0,26794,23268,58166,32324,75782,72486,8144,84105,10196,77434,0,39233,35157,5587,57693,25148,81370,97585,7757,57258,1079,144,0,0,38112,26770,85028,28126,96201,63068,49552,59763,4610,0,41350,18833,58656,46831,20142,27981,72543,9237,91688,7074,24511],[12249,69732,3449,76389,0,88928,93168,53914,50999,99128,39414,22767,73342,44169,96988,86309,71282,97794,44875,33825,96702,21797,36879,73228,6938,73743,14280,81086,87791,79766,58914,3585,24597,60941,52355,57966,25559,98738,94502,15069,53612,66902,70071,21117,34640,70872],[43782,31661,35262,40987,87141,43317,26428,9950,36960,32632,34472,0,56797,0,68284,18417,18805,1962,45239,86564,48349,89108,58004,0,62374,53963,79771,97385,85404,19636,40629,25676,13914,13505,4581,0,0,66921,34454,21433,9281,86295,60300,0,82206,47941],[28542,61409,48190,3134,97406,94972,63207,0,87927,0,47237,27303,51514,5107,25453,57810,30308,58612,0,0,85390,3013,92233,11725,33740,72753,33203,52736,70303,74033,77347,30396,502,10632,85307,9382,78819,89876,81499,97740,15047,14253,69228,30084,20071,0],[39001,33406,76907,81530,84700,70680,54033,39281,32652,82398,49787,56282,72812,11529,28980,19172,14358,68893,58061,85137,77756,0,81280,52321,82578,73064,21145,17998,53235,71460,27,19972,97210,28943,43647,27908,51156,173,0,2974,0,49195,30041,48457,76054,28490],[27301,5324,15202,41082,87023,63071,16074,5336,13856,80137,27937,51453,0,34522,78452,55800,83838,60072,34016,0,30341,44871,85893,18673,73204,26849,1580,49150,40963,91453,63924,34616,90584,18079,47058,35541,8630,14390,67643,22909,83907,31516,31006,49802,0,2971]]))
print(time.time()-t0)

t0 = time.time()
print(s.cutOffTree([[78286,75182,56288,96996,42333,13203,74081,74151,16154,18229,0,22253,52847,40861,21393,38736,50472,55793,61871,47951,0,44737,46989,2803,66270,94807,95378,1120,28431,30593,16481,35574,59747,17538,60254,47527],[83842,52564,14434,50711,86441,0,36252,7907,74121,39890,92460,0,0,29908,40579,89539,0,21630,36577,42183,54220,68214,9298,17550,61911,92627,8916,74444,33633,31991,99608,54985,41179,75697,98512,0],[13265,69519,16387,51517,25564,14781,21568,13771,1702,0,69089,30014,1276,0,65598,86904,25515,49369,29994,85707,5087,41937,34521,9734,72779,71990,56739,1793,19130,68970,94533,3771,87196,57304,93156,40213],[0,89157,12247,95535,40939,54509,17363,76328,22509,68437,64824,48335,98358,68041,88179,949,15213,13938,26617,79975,6352,0,95071,67770,79274,59181,20295,12942,8725,18158,77211,64768,0,0,6587,41108],[55255,59724,96323,234,8336,25035,71754,62063,0,38949,38895,0,45243,98637,43987,55466,65307,34169,19567,15523,89633,36035,86783,46066,21660,96813,3068,63504,81029,7136,23674,10131,51302,36649,72826,24004],[0,53502,78737,21082,16874,49118,21250,10214,85955,38219,58089,75339,72828,11207,0,8756,28492,72922,67057,15288,63374,37461,98840,11437,89000,68006,59954,4398,40380,7036,9091,3391,42556,0,40126,88928],[41294,33060,91856,43317,32659,37057,53659,45147,53013,68624,3732,15847,35570,73155,57833,24065,16867,54177,27303,0,0,33468,82275,31482,47526,82925,69610,48628,22263,40867,82603,97729,43609,4666,3888,27241],[39844,35948,66125,61443,85908,36271,97772,67468,42394,42585,49074,62694,64801,88632,92046,88377,2332,30778,36301,0,17344,37866,92506,44747,30873,49812,51556,62301,52272,85191,33634,43248,0,95403,11639,42617],[79854,56239,78226,39538,18733,55955,0,46764,16986,33025,90012,95070,81876,0,52584,57447,93284,15331,134,62295,84550,65795,19418,0,0,58984,89362,12429,86740,76298,94199,86430,53395,96560,41430,12281],[33285,731,35838,12095,43677,28517,95440,32575,58496,0,0,35874,17790,0,1249,31640,6235,28724,36196,0,18133,51417,88503,0,66813,56733,54017,0,41418,75079,61391,39372,84962,36321,63252,0],[85338,0,40334,45126,94920,0,67908,43603,11546,37521,34907,41049,47102,66021,22422,62540,73252,0,76051,28742,17190,43007,96062,4769,89589,96073,36723,78703,65021,0,63393,1282,1895,75214,14214,78267],[30048,50762,93675,98718,58675,48923,32800,46013,96180,17576,50402,4550,7732,25276,31420,22785,98326,58978,0,0,0,95054,6354,14569,63117,78665,0,46010,88437,43867,64806,29001,1975,7840,88155,93799],[72284,94656,62600,40512,69583,79084,91426,0,42508,46990,0,7614,26476,57328,0,37933,15306,70200,59042,92573,0,2990,13188,77543,33111,69980,0,669,65957,79366,56274,88007,0,15580,77606,42847],[0,53808,45093,68460,70131,13023,45348,44476,0,49897,0,91247,44085,7292,22412,23880,0,86957,73380,9891,23510,50019,19210,21105,95948,0,90449,76933,83183,83690,39555,50306,31697,55681,79907,74096],[0,0,52270,65870,8219,0,75003,62167,30765,25308,13181,55724,50434,83519,27576,11084,80222,7594,66728,51896,48338,0,4568,66933,56745,45627,99346,40375,30136,95878,0,27464,55677,92236,3019,75713],[0,51066,99890,55638,18340,81124,74639,20102,49046,21892,51619,53170,59984,11186,53818,8089,53604,17079,47965,0,22338,54762,52481,57690,52400,6517,42334,33058,93082,5853,91947,99845,12349,35090,0,4755],[63070,43592,79029,77695,0,54373,77414,72618,62286,0,51525,86657,0,0,59921,82203,90187,6704,91881,15113,33539,22710,11749,95857,78807,4907,69206,0,98146,64939,41007,46155,46178,14860,37857,80015],[14982,11686,34531,34407,64333,24034,59908,98289,87772,94114,37399,14985,22167,27666,26544,4078,0,0,28877,86725,6928,21620,84358,89614,82904,25160,28489,50774,10314,27510,2170,94041,22567,42424,41326,14927],[16172,0,31462,40500,26731,88764,86254,50629,26956,12234,45673,80785,69426,2714,88379,0,25925,59098,77776,9690,8172,61411,40221,97207,23140,36115,45293,27885,84661,65139,95030,0,35748,17545,0,0],[52314,0,38429,1538,64592,18080,70368,17863,59163,94120,16227,20606,26223,0,65138,38434,18640,0,87874,99682,57020,72007,43588,87919,98448,53889,0,9768,73290,8843,81723,31498,21850,0,17904,7982],[62569,93819,5972,54645,51142,13427,85848,80080,88619,74515,56022,67867,21162,94933,3149,5620,7507,97553,22725,2925,7505,14513,0,28256,10251,17517,58573,82848,41539,94267,82148,23633,80569,82391,44835,45620],[0,44167,95855,9145,4262,2017,36462,62805,489,64165,53698,58604,88833,88944,68536,97069,85774,86647,55373,24348,88297,28408,65323,28934,3309,91599,85718,91398,10445,34034,20880,53692,47458,81834,36888,54290],[14604,27441,78556,69080,39419,30453,15760,26727,81584,87703,5387,26588,0,74944,26521,63559,77847,56380,99291,57023,93989,74178,0,89973,79640,66052,21580,25838,36268,56816,55642,89992,81483,79948,60651,74938],[38339,0,57504,23231,0,82690,88665,12346,0,50558,54421,8853,45034,75764,3458,0,0,61050,76503,81878,92186,0,73079,65352,58849,39485,27106,78999,28859,48300,88487,45894,65860,32507,56532,47136],[41118,73506,10748,52760,0,83939,86088,18274,0,57339,74543,53088,79407,63811,4184,94664,6357,32105,78264,96267,82271,65843,76447,11988,41327,67640,36724,7603,14640,68598,94618,26046,83404,21148,0,12066],[82990,63008,82776,80677,68171,12806,74542,89236,58803,0,76311,23958,11547,17435,54100,75578,77979,24031,59321,84034,64754,4341,35923,29456,65588,90143,80987,94212,19513,87418,47778,97191,0,21337,22658,9668],[0,55412,30558,93036,83748,1110,55654,56981,9745,6892,40946,33996,66583,0,1982,79151,82277,41016,88963,2917,0,83236,98543,0,80929,27955,36343,0,17071,47478,47810,96805,17199,55644,78295,0],[0,50345,56766,26039,42826,68719,17779,27760,95139,0,33958,74382,29210,77560,21613,0,51281,49888,80087,45526,21004,77987,78988,59193,0,80108,90041,81625,112,0,19454,1759,22761,51604,36326,95319],[13577,0,40130,10781,73646,65923,12802,60109,0,52090,75970,85408,0,11656,20747,30208,51885,63197,44160,0,45882,52730,58073,66309,63010,87329,65777,60685,80843,47592,47417,1508,65272,0,42380,87370],[88214,91470,5128,44177,61788,86401,87040,96851,67185,56656,52457,7765,10272,89691,18850,5443,76425,9899,0,84608,73688,55639,19391,63576,35451,95993,0,62249,65134,9053,29790,71578,24785,66664,69072,0],[7741,62900,21537,58824,99737,35279,81283,0,9450,21697,50176,56785,23100,56718,93248,54336,35654,45552,36405,5295,43045,74969,88897,23570,82530,53403,93067,0,20566,86572,0,53207,0,74449,38328,21334],[2930,84499,49780,6249,22841,46583,79603,98334,91840,85599,46434,77811,79866,30077,41256,72884,0,51106,35784,49652,95732,3445,20737,53222,8622,36291,84132,17913,93639,83229,65556,0,50032,46830,40065,27718],[74438,66971,23733,70531,50905,81568,17457,749,15851,85428,71062,1726,29764,72275,0,31566,78532,74953,30124,48266,53295,65782,40128,75683,23667,63711,87731,54214,36694,39536,91105,4674,56917,13906,0,93793],[36490,14761,65349,36382,21439,10934,91228,9635,32165,80580,80088,56198,61281,51815,89835,98880,0,83806,19145,12419,26873,45908,98874,0,31584,44088,0,86545,62433,54425,5832,91790,56550,45740,81074,51164],[15201,0,12099,41437,86199,76065,55523,94854,82280,24435,5014,42376,38211,0,25765,82355,82154,38291,58929,17251,0,0,0,6911,97177,68801,67213,512,82220,70342,51123,24552,41098,96929,25747,64060],[19699,46914,42229,58899,37845,65732,80807,14812,89688,4019,95895,95691,373,20237,5628,0,89515,83237,67380,0,10541,0,81895,47911,49173,51836,17498,42099,73218,93404,54379,57122,16925,84184,62680,0],[83759,7303,73222,49883,49149,9558,49666,27866,2614,61594,37179,0,2937,41363,20169,0,37091,66739,81382,93998,67812,0,83574,3610,96511,89815,34356,52381,28048,52163,56496,78534,33359,89895,64657,6606],[68286,36263,61740,63501,0,92379,79309,84154,12039,24654,91239,61713,17173,68026,74147,53138,67312,46174,47425,27864,82344,38477,98696,0,8498,28648,10146,1893,82144,0,64849,64517,41038,63733,44240,69736],[45895,0,9398,59675,27485,26911,79051,55933,2187,74354,42350,23521,58570,56600,35252,90136,5797,73893,64028,0,37768,63721,0,95729,92130,12811,99181,18374,29679,91480,31586,25200,57058,63157,2178,36086],[69535,45983,49520,63346,96546,63370,94777,24390,3404,18351,73487,64731,79818,38501,69039,3325,97380,19459,48195,38053,11531,10765,41080,8408,76886,54510,4301,64329,31940,0,60135,90358,91615,26633,3825,49232],[84696,0,19751,0,0,21124,27839,3221,62637,0,49716,55117,0,20488,0,15342,71082,0,0,9678,45391,82922,28384,60830,9798,73980,65113,30713,75009,22111,91376,14243,68789,33731,92279,75640],[54570,53618,75676,10949,44247,37493,99877,28239,0,73792,0,48151,92330,53124,63502,90216,29639,38874,45252,50983,69589,47457,24431,61410,51796,20183,17775,66834,0,41980,86322,79585,98349,54238,19784,37975],[27822,96710,49305,26520,70576,20190,56951,28054,94896,91032,7659,70964,56920,39286,0,52300,94615,35253,0,27830,0,36113,99701,47724,85851,6793,8677,90617,1152,14181,15993,78368,97223,51404,21803,46896],[10073,0,72595,21692,2811,72448,24948,0,44520,0,38970,0,36620,90729,90534,50976,8868,98900,28481,52045,49890,51257,96051,81582,34406,57712,47970,66808,98160,10612,14470,63160,42865,29038,43215,92065],[81729,32082,91405,58111,30723,53083,0,57944,19441,17228,42244,63328,30516,33819,1790,18697,11545,26207,5261,44832,23162,49672,36879,60916,73460,3678,33127,8352,72587,77922,1150,61149,38584,61016,14391,0],[3619,59055,38482,11116,0,58683,0,56180,87474,87650,25047,0,26694,41580,1691,59684,78934,38798,49479,3516,85992,0,58255,86278,62239,63503,21624,53729,63603,89822,37594,12553,78183,50016,67217,98423],[98076,16988,52766,46048,8715,10780,52448,1515,77766,10104,88493,98414,68021,17911,82419,96436,20341,45310,63109,81401,80628,15028,0,40563,95923,51199,42118,84860,44248,38300,89273,8887,27858,23326,89506,99894],[3270,70718,7801,67547,36937,4536,47853,8759,25649,19600,95120,16225,0,21546,9927,45725,11500,16546,1396,31430,83047,79946,488,68403,86958,54695,415,22235,96016,82184,649,95375,5239,7900,4326,32716],[9747,47603,60637,16614,96410,84194,90071,34204,58936,34185,39129,91409,94932,16821,96686,72208,13750,99561,80671,66018,68791,76308,13425,18072,68296,64652,84700,69221,0,14223,43918,66455,349,14868,66032,61379]]))
print(time.time() - t0)
